#include"cds_btree.h"
#include"cds_common.h"
#include"cds_list.h"
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<strings.h>
#include<assert.h>
#ifdef __cplusplus
extern "C" {
#endif

//搜索key,将找到的节点指针放进nodep变量，关键字所在节点的下标放进index
static void  __btree_search(btree_t * tree, unsigned long key , btree_node_t ** nodep,int *index);
//获取左子树的最大节点
static btree_node_t * __get_last(btree_node_t * node);
//获取子树的最小节点
static btree_node_t * __get_first(btree_node_t * node);
//获取子节点在父节点中的下标 
static int __get_index_in_parent(btree_node_t * child,btree_node_t * parent );
//左旋
static void __left_rotate(btree_node_t * node, int index );
//右旋
static void __right_rotate(btree_node_t * node, int index );
//合并(合并到左子节点上)
static void __merge(btree_t * tree, btree_node_t * node, int index);
//删除后失衡时调用的平衡函数
static void __balance_for_del(btree_t * tree, btree_node_t * node);
//插入
static btree_node_t *  __insert( btree_t * tree, btree_node_t * node, btree_keyword_t keyword,  btree_node_t * right_child );
//插入后失衡时调用的平衡函数
static void  __balance_for_insert(btree_t * tree, btree_node_t * node);
//删除node节点中的关键字key,key在node节点的index位置
static void __btree_del(btree_t * tree, unsigned long key, btree_node_t * node, int index );


//************** the api implementation ************************

//B树的插入
void * btree_insert( btree_t * tree, unsigned long key, void * data ){
    btree_node_t * node = tree->root;
    //如果树为空树,即根节点为NULL
    if(!node){
        node = malloc(sizeof(btree_node_t)); 
        tree->root = node;
        tree->size = 1; 
        node->leaf = 1; 
        node->num = 1; 
        node->parent = NULL; 
        node->keywords[0].key = key;
        node->keywords[0].data = data;
        return NULL;
    }
    for(int i=0;;i++){
        //找到了叶子节点上
        if(node->leaf){
            break;
        }
        int i=0;
        //找到往下层去的指针下标
        for(;i<node->num;i++){
            if(key<node->keywords[i].key){
               break;
            }else if(key == node->keywords[i].key){
                return node->keywords[i].data;
            }
        }
        //往下层迭代
        node = node->children[i];
    }

    //到此就找到了叶子节点node

    //看看叶子节点上是否存在相同key,如果有则返回这个已存在的数据，不执行本次插入
    for(int i=0;i<node->num;i++){
        if(key==node->keywords[i].key){
            return node->keywords[i].data;
        }
    }

    //执行插入
    btree_node_t * ret = __insert(tree,node, (btree_keyword_t){key,data},NULL);

    //如果该叶子节点中关键字数量超过了,则执行分裂平衡
    if(ret->num>MAX){ 
        __balance_for_insert(tree, ret);
    }
    //统计量加1
    tree->size++;
    return NULL; 
}

//B树的搜索
void * btree_search(btree_t * tree, unsigned long key ){
    btree_node_t * node = NULL;
    int index = -1;
    __btree_search(tree, key, &node, &index );
    if(node){
        return node->keywords[index].data;
    }
    return NULL;
}

//B树的删除
void * btree_del(btree_t * tree, unsigned long key ){
    btree_node_t * node = NULL;
    int index = -1;
    __btree_search(tree, key, &node,&index );
    if(node){
        debug("delete %lu\n",node->keywords[index].key);
        void * data = node->keywords[index].data;
        __btree_del(tree,key, node,index);
        return data;
    }
    return NULL;
}

//B树的中序遍历
void btree_travel_middle( btree_t * tree ,travel_func_t travel){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    btree_node_t * node = __get_first(tree->root);
    for(int idx=0;node;){
        if(node->leaf){
            for(int i=0;i<node->num;i++){
                travel(node->keywords[i].key,node->keywords[i].data );
            }
            idx  = __get_index_in_parent(node,node->parent);
            node = node->parent; 
        }else{
            if(idx>=node->num){
                idx  = __get_index_in_parent(node,node->parent);
                node = node->parent;
            }else{
                travel(node->keywords[idx].key,node->keywords[idx].data ); 
                node = __get_first(node->children[idx+1]);
            }
        }
        if(node==tree->root && idx>=node->num){
            break;
        }
    }
}

//B树的层次打印关键字
void btree_print_tree( btree_t * tree){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    struct list_head head = LIST_HEAD_INIT(head);

    struct list_head * new = malloc(sizeof(struct list_head)+sizeof(btree_node_t *));
    *(btree_node_t **)(((char *)new)+sizeof(struct list_head)) = tree->root;

    list_add_head(new, &head);
    int nr=0;
    int sub_nr = 1 ;
    int new_level_flag = 1 ;
    int nr_level = 0;
    int cnt;
    for(cnt=0;!list_is_empty(&head);){

       if(new_level_flag){
            nr_level++;
            new_level_flag = 0;
            nr = sub_nr;
            sub_nr = 0;
            printf("\n--level:<%d>-----------------------------------------------------------------------\n",nr_level);
        }
        nr--;
        if(nr==0){
            new_level_flag = 1;
        }
        struct list_head * out_node = list_del_last(&head);
        btree_node_t * node = *(btree_node_t **)(((char *)out_node)+sizeof(struct list_head));
         
        sub_nr += node->num+1;
        if(node==tree->root)
            assert(node->num<=MAX && node->num>0 );
        else
            assert(node->num<=MAX && node->num>=MIN);
        if(!node->leaf){
            for(int i=0;i<node->num+1;i++){
                if(!out_node){
                    out_node = malloc(sizeof(struct list_head)+sizeof(btree_node_t *));
                }
                assert(node->children[i]->parent==node);  
                
                *(btree_node_t **)(((char *)out_node)+sizeof(struct list_head)) = node->children[i]; 
                list_add_head(out_node,&head); 
                out_node = NULL;  
            }
        }
        printf(" [ ");
        for(int i=0;i<node->num;i++){
            cnt++;
            printf("%lu ",node->keywords[i].key);
        }
        printf("] ");
        if(out_node){
            free(out_node);
        }
    }
    printf("\ntotal number of levels: %d,total of data: %d\n",nr_level,cnt);
}

//B树的层次遍历
void btree_travel_level( btree_t * tree, travel_func_t travel ){
    if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    struct list_head head = LIST_HEAD_INIT(head);
    struct list_head * new = malloc(sizeof(struct list_head)+sizeof(btree_node_t *));
    *(btree_node_t **)(((char *)new)+sizeof(struct list_head)) = tree->root;
    list_add_head(new, &head);
    while(!list_is_empty(&head)){
        struct list_head * out_node = list_del_last(&head);
        btree_node_t * node = *(btree_node_t **)(((char *)out_node)+sizeof(struct list_head));
        if(!node->leaf){
            for(int i=0;i<node->num+1;i++){
                if(!out_node){
                    out_node = malloc(sizeof(struct list_head)+sizeof(btree_node_t *));
                }
                *(btree_node_t **)(((char *)out_node)+sizeof(struct list_head)) = node->children[i]; 
                list_add_head(out_node,&head); 
                out_node = NULL;  
            }
        }
        for(int i=0;i<node->num;i++){
            travel(node->keywords[i].key,node->keywords[i].data);
        }
        if(out_node){
            free(out_node);
        }
    }
}

//B树的清空方法,采用层次遍历来清空
void btree_clear( btree_t * tree, destroy_func_t destroy ){
   if(!tree->root){
        debug("the tree is empty now!\n");
        return;
    }
    struct list_head head = LIST_HEAD_INIT(head);
    struct list_head * new = malloc(sizeof(struct list_head)+sizeof(btree_node_t *));
    *(btree_node_t **)(((char *)new)+sizeof(struct list_head)) = tree->root;
    list_add_head(new, &head);
    while(!list_is_empty(&head)){
        struct list_head * out_node = list_del_last(&head);
        btree_node_t * node = *(btree_node_t **)(((char *)out_node)+sizeof(struct list_head));
        if(!node->leaf){
            for(int i=0;i<node->num+1;i++){
                if(!out_node){
                    out_node = malloc(sizeof(struct list_head)+sizeof(btree_node_t *));
                }
                *(btree_node_t **)(((char *)out_node)+sizeof(struct list_head)) = node->children[i]; 
                list_add_head(out_node,&head); 
                out_node = NULL;  
            }
        }
        for(int i=0;i<node->num;i++){
            destroy(node->keywords[i].data);
            tree->size--;
        }
        free(node);
        node = NULL;
        if(out_node){
            free(out_node);
        }
    }
    tree->root = NULL;
}

//************* the static functions ***************************

static btree_node_t * __get_last(btree_node_t * node ){
    while(!node->leaf){
        node = node->children[node->num];
    }
    return node;
}

//左旋
static void __left_rotate(btree_node_t * node, int index ){
    //左子节点
    btree_node_t * left_child = node->children[index];
    //右子节点
    btree_node_t * right_child = node->children[index+1];
    // 父节点的index位置的keyword放到左子节点的keywords尾部
    left_child->keywords[left_child->num++] = node->keywords[index];
    // 右子节点的首孩子指针放到左子节点的children尾部
    left_child->children[left_child->num] = right_child->children[0];
    // 如果挪过来的子节点指针不为NULL,则要更新它的parent指针
    if(!right_child->leaf ){
        left_child->children[left_child->num]->parent = left_child;
    }
    //右节点的首keyword放到父节点的index位置
    node->keywords[index] = right_child->keywords[0];
    //右子节点的剩下keywords前移一格
    //memmove(right_child->keywords,right_child->keywords+1,sizeof(btree_keyword_t)*(right_child->num-1) );
    for(int j=0;j<right_child->num-1;j++){
        right_child->keywords[j] = right_child->keywords[j+1];
    }
    //右子节点的剩下children前移一格
    //memmove(right_child->children,right_child->children+1,sizeof(btree_node_t*)*(right_child->num) );
    for(int t=0;t<right_child->num;t++){
        right_child->children[t] = right_child->children[t+1];
    }
    //右子节点统计量减一
    right_child->num--;
}

//右旋
static void __right_rotate(btree_node_t * node, int index ){
    //左子节点
    btree_node_t * left_child = node->children[index];
    //右子节点
    btree_node_t * right_child = node->children[index+1];
    //右子节点所有keywords后移一格
    //memmove(right_child->keywords+1,right_child->keywords,sizeof(btree_keyword_t)*(right_child->num) );
    for(int x=0;x<right_child->num;x++){
        right_child->keywords[right_child->num-x] = right_child->keywords[right_child->num-x-1]; 
    }
    //右子节点所有children后移一格
    //memmove(right_child->children+1,right_child->children,sizeof(btree_node_t*)*(right_child->num+1) );
    for(int y=0;y<right_child->num+1;y++){
        right_child->children[right_child->num+1-y] = right_child->children[right_child->num-y];
    }
    // 父节点的index位置的keyword放到右子节点的keywords首位置
    right_child->keywords[0] = node->keywords[index];
    // 左子节点的尾孩子指针放到右子节点的children首部
    right_child->children[0] = left_child->children[left_child->num]; 
    // 右子节点统计量加1
    right_child->num++;
    // 如果挪过来的子节点指针不为NULL,则要更新它的parent指针
    if(!left_child->leaf){
        right_child->children[0]->parent = right_child;
    }
    //左节点的尾keyword放到父节点的index位置
    node->keywords[index] = left_child->keywords[--left_child->num];
}

//合并,往左子节点合并
static void __merge(btree_t * tree, btree_node_t * node, int index){
    //左子节点
    btree_node_t * left_child = node->children[index];
    //右子节点
    btree_node_t * right_child = node->children[index+1];
    //父节点的index位置的关键字下到左子节点
    left_child->keywords[left_child->num++] = node->keywords[index];
    //右子节点的所有关键字移到左子节点
    memmove(left_child->keywords+left_child->num,right_child->keywords, sizeof(btree_keyword_t)*right_child->num);
    memmove(left_child->children+left_child->num,right_child->children, sizeof(btree_node_t*)*(right_child->num+1));
    //更新挪动的child的父指针
    if(!right_child->leaf){
        for(int i=0;i<right_child->num+1;i++){
            right_child->children[i]->parent = left_child;
        }
    }
    //更新左子节点的统计量
    left_child->num += right_child->num;
    //父节点的index位置的后边关键字要替补上来
    if(index<node->num-1){
        memmove(node->keywords+index,node->keywords+index+1, sizeof(btree_keyword_t)*(node->num-index-1));
        memmove(node->children+index+1, node->children+index+2, sizeof(btree_node_t*)*(node->num-index-1));
    }
    //父节点统计量减1
    node->num--;
    //释放右子节点
    free(right_child);
}

//删除后的平衡函数
static void __balance_for_del(btree_t * tree, btree_node_t * node){
    debug("执行平衡处理...node.num:%d\n",node->num);
    int i=0;
    while(node->num<MIN){
        debug("平衡次数: i=%d\n",++i);
        //找到node在父节点中的指针下标
        btree_node_t * parent = node->parent;
        int idx = 0;
        for(;idx<parent->num+1;idx++){
            if(parent->children[idx] == node){
                break;
            }
        }
        //情况一: 如果有右兄弟，且右兄弟有多于MIN个关键字，则执行左旋借
        if(idx<parent->num){
            btree_node_t * right_brother = parent->children[idx+1];
            if(right_brother->num > MIN ){
                debug("向右兄弟借\n");
                __left_rotate(parent,idx); 
                break;
            }
        }
        //情况二: 如果有左兄弟，且左兄弟有多于MIN个关键字，则执行右旋借
        if( idx>0 ){
            btree_node_t * left_brother = parent->children[idx-1];
            if(left_brother->num > MIN ){
                debug("向左兄弟借\n");
                __right_rotate(parent,idx-1);
                break;
            }
        }
        //情况三: 左右兄弟都不够借,则执行合并,
        if(idx>0){
            debug("左合并\n");
            __merge(tree, parent,idx-1);
        }else{
            debug("右合并\n");
            __merge(tree, parent,idx);
        }
        //如果parent是树根节点且节点数为0,表示根节点没有关键字了，这时候要root指针指向parent的children[0]
        if(parent==tree->root){
            if( parent->num==0 ){
                debug("parent->num is 0 \n");
                tree->root = parent->children[0];
                tree->root->parent = NULL;
                free(parent);
            }
            debug("go out from parent is root\n");
            break;
        }
        node = parent;
    }
}

//删除node节点的index位置的关键字
static void __btree_del(btree_t * tree, unsigned long key, btree_node_t * node, int index ){
    //如果node不是叶子节点,换成叶子节点
    if( !node->leaf ){
        debug("换到叶子去...\n");
        //找到左子树最大节点
        btree_node_t * left_max = __get_last(node->children[index]);
        //交换关键字
        btree_keyword_t tmp = node->keywords[index];
        node->keywords[index] = left_max->keywords[left_max->num-1];
        left_max->keywords[left_max->num-1] = tmp;
        node = left_max;
        index = node->num-1;
    }
    //接下来node一定是叶子节点

    //先做删除动作
    //如果关键字位置是最后一个,则只需要node->num减一即可
    if(index<node->num-1){
        //关键字不在最后一个位置的情况下，index后边的替上来即可
        for(int i=0;i<node->num-1-index;i++){
            node->keywords[index+i] = node->keywords[index+i+1];
        }
    }
    node->num--;
    tree->size--;
    //如果node的关键字数量大于MIN,则直接删除
    if(node->num >= MIN){
        debug("关键字有余地，直接删了!\n");
        return;
    }
    
    if(node==tree->root){//否则如果是树根节点
        //如果树根没有关键字,则树要变成空树,释放node指针
        if( node->num == 0  ){
            debug("删树根了!\n");
            free(node);
            tree->root = NULL;
            tree->size = 0;
        }
        debug("删到了树根上的关键字了!\n");
        return;
    }

    //执行平衡函数
    __balance_for_del(tree, node);
}

//获得子树最小节点
static btree_node_t * __get_first(btree_node_t * node){
    while(!node->leaf){
        node=node->children[0];
    }
    return node;
}


static int __get_index_in_parent(btree_node_t * child,btree_node_t * parent ){
    for(int x=0;x<parent->num+1;x++){
        if(parent->children[x]==child){
            return x;
        }
    }
    return -1;
}

static void  __balance_for_insert(btree_t * tree, btree_node_t * node){
    while(node->num>MAX){
        int idx = (node->num+1)/2-1; 
        btree_node_t * new_node = malloc(sizeof(btree_node_t));
        new_node->num = 0;
        new_node->leaf = node->leaf;
        new_node->parent = node->parent;
        //要搬移的关键字数量
        int cnt = node->num - idx - 1; 
        for(int i=0;i<cnt;i++){
            new_node->keywords[i] = node->keywords[idx+1+i]; 
        }
        new_node->num += cnt;
        node->num -= cnt+1;
        //要搬移的子节点指针数量为cnt+1
        if(!node->leaf){
            for(int i=0;i<cnt+1; i++){
                new_node->children[i] = node->children[idx+1+i];
                new_node->children[i]->parent = new_node;
            }
        }
        //如果不存在父节点，则新建一个父节点 
        if(!node->parent){
            btree_node_t * parent = malloc(sizeof(btree_node_t));
            parent->keywords[0] = node->keywords[idx];
            parent->children[0] = node;
            parent->children[1] = new_node;
            parent->num=1;
            parent->leaf = 0;
            parent->parent = NULL;
            node->parent = parent;
            new_node->parent = parent;
            tree->root = parent;
            break;
        }
        //将node中多出来的关键字插入父节点中
        node =  __insert(tree,node->parent,node->keywords[idx], new_node);
    }
}

static void  __btree_search(btree_t * tree, unsigned long key , btree_node_t ** nodep,int *index){
    btree_node_t * node = tree->root;
    if(!node){
        debug("B树为空,找不到关键字[%lu]\n",key);
        return ;
    }
    while(node){
        int i = -1; 
        for(i=0;i<node->num;i++){
            if(key < node->keywords[i].key){
                break;
            }else if( key == node->keywords[i].key ){
                //找到关键字了，返回位置
                *nodep = node;
                *index = i;
//开调试时，输出找到的关键字所在节点的keywords数组
#ifdef DEBUG
                for(int t=0;t<node->num;t++){
                    printf("%lu\t",node->keywords[t].key);
                }
                printf("\n");
#endif
                return;
            }
        }
        if(!node->leaf){
            if(i==node->num)
                debug("从第%d个子节点[%lu]的右指针进入\n",i-1,node->keywords[i-1].key);
            else
                debug("从第%d个子节点[%lu]的左指针进入\n",i,node->keywords[i].key);
            node = node->children[i];
        }else{
            debug("找不到关键字[%lu]\n",key);
            return ;
        }
    }
}

//插入之后，返回这个节点
static btree_node_t *  __insert( btree_t * tree, btree_node_t * node, btree_keyword_t keyword,  btree_node_t * right_child ){
    //定位插入位置
    int i = 0;
    for(;i<node->num;i++){
        if(keyword.key<node->keywords[i].key){
            break;
        }
    }
    //插入位置的数据往后挪
    memmove(node->keywords+i+1, node->keywords+i,
            sizeof(btree_keyword_t)*(node->num-i ));
    node->keywords[i] = keyword;  
    if(!node->leaf){
        memmove(node->children+i+2,node->children+i+1,
            sizeof(btree_node_t*)*(node->num-i)); 
        node->children[i+1] = right_child; 
    }
    node->num++;
    assert(node->num<=MAX+1);
    return node;
}

#ifdef __cplusplus
}
#endif


